#pragma once
#include<iostream>
#include<string>
#include<iomanip>
#include<istream>
#include<ostream>

using namespace std; 


template<class INFO>

struct Node
{
	INFO info;
	Node<INFO> *next;

	Node()
	{
		next = nullptr;
	}
	Node(INFO info)
	{
		this->info=info;
		this->next = nullptr;
	}
};

template< class INFO>
class List
{
	class Iterator
	{
	public:
		typedef Iterator self_type;
		typedef Node<INFO> value_type;
		typedef Node<INFO>& reference;
		typedef Node<INFO>* pointer;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		Iterator(pointer ptr) : ptr_(ptr) { }

		self_type operator++() { self_type i = *this; ptr_=ptr_->next; return i; }
		self_type operator++(int junk) { ptr_=ptr_->next; return *this; }
		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }
		bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
		bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }

	private:
		pointer ptr_;
	};
private:
	Node<INFO> *head;
	Node<INFO> *next;
	Node<INFO> *tail;
public:

	List()
	{
		head=tail=nullptr;
	}

	~List(void)
	{
		Node <INFO> *n = head;
		Node <INFO> *d;
		while (e != nullptr)
		{
			d =n;
			n = n -> next;
			delete d;
		}
	}

	void add_at_head(INFO info)
	{
		if(head == nullptr)
			head = tail = new Node<INFO>(info);
		else
		{
			Node<INFO> *n = new Node<INFO>(info);
			n->next = head;
			head= n;
		}
	}

	Node <INFO> *search(INFO info)
	{
		Node<INFO> *n = head;
		if (n == nullptr)
			return nullptr;
		else
		{
			do
			{
				if (n->info== info)
					return n;
				n = n->next;
			} 
			
			while (n != nullptr);
		}
		return nullptr;
	}

	Iterator begin()
	{
		return Iterator(head);
	}

	Iterator end()
	{
		return Iterator(nullptr);
	}

	/*void  remove(Node<INFO> *info)
	{
	Node<INFO> b = nullptr;
	if(info == nullptr || head == nullptr)
	{
	return ;
	}
	else if (info == head && head == tail)
	{
	delete info; 
	head= tail = nullptr;
	}
	else if (info == head)
	{
	head = head->next;
	delete info;
	}

	else if (info == tail)
	{
	b = nodebefore(info);
	b->next = nullptr;
	tail = b;
	delete info;
	}
	else
	{
	b = nodebefore(info);
	b->next = info->next;
	delete info;
	}
	}
	*/

	string Str (INFO info)
	{
		ostringstream oss;
		Node<INFO> *n = head;
		if (n == nullptr)
		{
			return "";
		}
		else
		{
			do
			{
				oss << n -> next;
				n = n -> next;
			}
			while(n != nullptr);
		}
		return oss.str();
	}

	friend istream &operator >>(istream &in, INFO &info)
	{
		in >> info >> skipws;
		return in;
	}

	friend ostream &operator <<(ostream &out, List<INFO> &list)
	{
		Node<INFO> *n = list.head;
		while ( n != nullptr)
		{
			out << n->info << " ";
			n = n-> next;
		}
		return out;
	}
};

